/*
题目: 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

https://leetcode.cn/problems/non-overlapping-intervals
 */
public class EraseOverlapIntervals {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]> () {
            // 贪心思路: 优先执行最早结束的
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[1] - o2[1];
            }
        });

        int src = 0; // 找出最少重叠的会议数量
        int prevEnd = intervals[0][0] - 1;
        for (int[] elem : intervals) {
            if (elem[0] >= prevEnd) {  // 如果开始时间大于结束时间, 就可以执行这个会议
                src ++;
                prevEnd = elem[1];
            }
            // 如果结束时间 > 开始时间, 就不执行这个会议
        }

        return intervals.length - src;
    }
}
